package 中等.双指针;

/**
 * 给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。
 * 同构字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。
 * 子字符串 是字符串中的一个连续字符序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/count-number-of-homogenous-substrings
 */
public class 统计同构子字符串的数目_1759 {

    public static void main(String[] args) {

        System.out.println(countHomogenous2("abbcccaa"));

    }

    /**
     * 统计以 s.chatAt(i) 结尾的同构字符串的数量
     * 计算方法为前面相邻==s.chatAt(i)的长度
     */
    public static int countHomogenous(String s) {
        int count = 0;

        char[] chars = s.toCharArray();
        for (int r = 0; r < chars.length; r++) {
            int l = r - 1;
            while (l >= 0 && chars[l] == chars[r]) l--;

            count += r - l;

            if (count >= 1000000007) {
                count -= 1000000007;
            }
        }

        return count;
    }


    /**
     * 双指针
     * 如果右指针 s[r]==s[r-1] ,那么左指针 l 不变
     * 否则 l=r
     * [l,r] 中始终只有一个类型的字符
     */
    public static int countHomogenous2(String s) {
        int count = 1;
        char[] chars = s.toCharArray();

        int l = 0;
        for (int r = 1; r < chars.length; r++) {
            if (chars[r] != chars[r - 1]) {
                l = r;
            }

            count += r - l + 1;

            if (count >= 1000000007) {
                count -= 1000000007;
            }
        }
        return count;
    }

}
